package com.xiaoyu.binaryTree;

/**
 * @program: DS_and_A
 * @description:
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。
 * 这条路径可能穿过也可能不穿过根结点。
 *
 * 示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 * 返回3, 它的长度是路径 [4,2,1,3] 或者[5,2,1,3]。
 *
 *            1
 *           /
 *          2
 *         / \
 *        4   5
 *       /     \
 *      6      7     --> 返回4 --> 6,4,2,5,7
 *
 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
 *
 *
 * 解法与124题,687题相似
 *
 * @author: YuWenYi
 * @create: 2021-06-06 11:41
 **/
public class DiameterOfBinaryTree_543 {
    //就是左子树的深度-1+右子树的深度-1就等于所谓直径
    private int maxDiameter;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null) return 0;
        //深度等于该节点的左子树高度+右子树高度
        int diameter = maxDepth(root.left) + maxDepth(root.right);

        maxDiameter = Math.max(maxDiameter, diameter);
        //对每一个结点都求diameter,然后直到找到最大的diameter
        diameterOfBinaryTree(root.left);
        diameterOfBinaryTree(root.right);

        return maxDiameter;
    }

    public int maxDepth(TreeNode root){
        if (root != null)
            return Math.max(root.left == null ? 0 : maxDepth(root.left),
                    root.right == null ? 0 : maxDepth(root.right)) + 1;
        return 0;
    }

    //解法二:
    int max=0;
    public int diameterOfBinaryTree1(TreeNode root) {
        depth(root);
        return max;
    }
    public int depth(TreeNode node){
        if(node==null){
            return 0;
        }
        int Left = depth(node.left);
        int Right = depth(node.right);
        max=Math.max(Left+Right,max);//将每个节点最大直径(左子树深度+右子树深度)当前最大值比较并取大者
        return Math.max(Left,Right)+1;//返回节点深度,注意这里是返回单侧的长度!!
    }


    public static void main(String[] args) {
        TreeNode right = new TreeNode(3);
        //TreeNode right1 = new TreeNode(3,new TreeNode(6),new TreeNode(7));
        TreeNode left = new TreeNode(2,null,right);
        TreeNode root = new TreeNode(1,left,null);

        DiameterOfBinaryTree_543 diameterOfBinaryTree_543 = new DiameterOfBinaryTree_543();
        System.out.println(diameterOfBinaryTree_543.diameterOfBinaryTree(root));
    }
}
